namespace ds
{
    /**
     * @typedef {Object} Callbacks
     *
     * @property {function(vertices: Object): boolean} [allowTraversal] -
     *  Determines whether DFS should traverse from the vertex to its neighbor
     *  (along the edge). By default prohibits visiting the same vertex again.
     *
     * @property {function(vertices: Object)} [enterVertex] - Called when DFS enters the vertex.
     *
     * @property {function(vertices: Object)} [leaveVertex] - Called when DFS leaves the vertex.
     */

    /**
     * @param {Callbacks} [callbacks]
     * @returns {Callbacks}
     */
    function initCallbacks(callbacks: {
        enterVertex?: ({ currentVertex, previousVertex }) => void,
        leaveVertex?: ({ currentVertex, previousVertex }) => void,
        allowTraversal?: ({ currentVertex, previousVertex, nextVertex }) => boolean
    } = {})
    {
        const initiatedCallback: {
            enterVertex: ({ currentVertex, previousVertex }) => void,
            leaveVertex: ({ currentVertex, previousVertex }) => void,
            allowTraversal: ({ currentVertex, previousVertex, nextVertex }) => boolean
        } = <any>callbacks;

        const stubCallback = () => { };

        const allowTraversalCallback = (
            () =>
            {
                const seen = {};
                return ({ nextVertex }) =>
                {
                    if (!seen[nextVertex.getKey()])
                    {
                        seen[nextVertex.getKey()] = true;
                        return true;
                    }
                    return false;
                };
            }
        )();

        initiatedCallback.allowTraversal = callbacks.allowTraversal || allowTraversalCallback;
        initiatedCallback.enterVertex = callbacks.enterVertex || stubCallback;
        initiatedCallback.leaveVertex = callbacks.leaveVertex || stubCallback;

        return initiatedCallback;
    }

    /**
     * @param {Graph} graph
     * @param {GraphVertex} currentVertex
     * @param {GraphVertex} previousVertex
     * @param {Callbacks} callbacks
     */
    function depthFirstSearchRecursive<T>(graph: Graph<T>, currentVertex: GraphVertex<T>, previousVertex: GraphVertex<T>,
        callbacks: {
            enterVertex: ({ currentVertex, previousVertex }) => void,
            leaveVertex: ({ currentVertex, previousVertex }) => void,
            allowTraversal: ({ currentVertex, previousVertex, nextVertex }) => boolean
        })
    {
        callbacks.enterVertex({ currentVertex, previousVertex });

        graph.getNeighbors(currentVertex).forEach((nextVertex) =>
        {
            if (callbacks.allowTraversal({ previousVertex, currentVertex, nextVertex }))
            {
                depthFirstSearchRecursive(graph, nextVertex, currentVertex, callbacks);
            }
        });

        callbacks.leaveVertex({ currentVertex, previousVertex });
    }

    /**
     * @param {Graph} graph
     * @param {GraphVertex} startVertex
     * @param {Callbacks} [callbacks]
     */
    export function depthFirstSearch<T>(graph: Graph<T>, startVertex: GraphVertex<T>, callbacks: {
        enterVertex?: ({ currentVertex, previousVertex }) => void,
        leaveVertex?: ({ currentVertex, previousVertex }) => void,
        allowTraversal?: ({ currentVertex, previousVertex, nextVertex }) => boolean
    } = {})
    {
        const previousVertex: GraphVertex<T> = null;
        depthFirstSearchRecursive(graph, startVertex, previousVertex, initCallbacks(callbacks));
    }

}